#leetcode题目394：字符串解码
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：栈

class Solution:
    def decodeString(self, s: str) -> str:
        """
        字符串解码
        给定一个经过编码的字符串，返回它解码后的字符串。
        编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
        注意 k 保证为正整数。
        你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
        此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k 。
        例如不会出现像 3a 或 2[4] 的输入。
        """
        curr = []  # 当前正在构建的字符串，对应Java的StringBuilder curr
        stack = []  # 存储字符串的栈，对应Java的Deque<String> stack
        stack_count = []  # 存储重复次数的栈，对应Java的Deque<Integer> stackCount
        count = 0  # 当前解析的数字，对应Java的int count
        
        for char in s:
            if '0' <= char <= '9':
                # 如果是数字，构建重复次数
                count = count * 10 + int(char)
            elif 'a' <= char <= 'z':
                # 如果是小写字母，添加到当前字符串
                curr.append(char)
            elif char == '[':
                # 遇到左括号，保存当前状态
                stack.append(''.join(curr))  # 将当前字符串转换为字符串并压栈
                stack_count.append(count)    # 将重复次数压栈
                curr = []                    # 重置当前字符串
                count = 0                    # 重置计数
            elif char == ']':
                # 遇到右括号，处理重复
                loop = stack_count.pop()     # 弹出重复次数
                t = []                       # 临时字符串构建器
                
                # 将当前字符串重复loop次
                for _ in range(loop):
                    t.extend(curr)
                
                # 弹出之前的字符串并与重复后的字符串合并
                prev_string = stack.pop()
                curr = list(prev_string) + t
        
        return ''.join(curr)

#测试数据
s = "3[a]2[bc]"
#预期输出："aaabcbc"
solution = Solution()
print(solution.decodeString(s))

s = "3[a2[c]]"
#预期输出："accaccacc"
solution = Solution()
print(solution.decodeString(s))

